class Solution {
public:
    static const int INF=0x3f3f3f3f;

    int minimumCoins(vector<int>& prices) {
        int n=prices.size();

        int dp[n+1][2];
        memset(dp,INF,sizeof(dp));
        dp[1][1]=prices[0];
        for(int i=1;i<n;i++)
        {
            dp[i+1][1]=prices[i]+min(dp[i][0],dp[i][1]);

            for(int j=i;j+j>=i+1;j--)
            {
                dp[i+1][0]=min(dp[j][1],dp[i+1][0]);
            }
        }
        return min(dp[n][0],dp[n][1]);
    }
};
